#pragma once
#include <iostream>
#include <vector> 
#include <algorithm>

using namespace std;
void Quick_Sort(vector<int>& arr, int begin, int end){
    if(begin > end)
        return;
    int tmp = arr[begin];
    int i = begin;
    int j = end;
    while(i != j){
        while(arr[j] >= tmp && j > i)
            j--;
        while(arr[i] <= tmp && j > i)
            i++;
        if(j > i){
            int t = arr[i];
            arr[i] = arr[j];
            arr[j] = t;
        }
    }
    arr[begin] = arr[i];
    arr[i] = tmp;
    Quick_Sort(arr, begin, i-1);
    Quick_Sort(arr, i+1, end);
}

void max_heapify(vector<int>& arr, int start, int end) {
    int dad = start;
    int son = dad * 2 + 1;
    while (son <= end) { 
        if (son + 1 <= end && arr[son] < arr[son + 1]) 
            son++;
        if (arr[dad] > arr[son])
            return;
        else { 
            swap(arr[dad], arr[son]);
            dad = son;
            son = dad * 2 + 1;
        }
    }
}
void heap_sort(vector<int>& arr, int len) {
    for (int i = len / 2 - 1; i >= 0; i--)
        max_heapify(arr, i, len - 1);
    for (int i = len - 1; i > 0; i--) {
        swap(arr[0], arr[i]);
        max_heapify(arr, 0, i - 1);
    }
}
/**
 * Quicksort algorithm (driver).
 */
 template <typename Comparable>
 void quicksort( vector<Comparable> & a )
 {
 	quicksort( a, 0, a.size( ) - 1 );
 }
/**
 * Return median of left, center, and right.
 * Order these and hide the pivot.
 */
template <typename Comparable>
const Comparable & median3( vector<Comparable> & a, int left, int right )
{
	int center = ( left + right ) / 2;

	if( a[ center ] < a[ left ] )
		std::swap( a[ left ], a[ center ] );
	if( a[ right ] < a[ left ] )
		std::swap( a[ left ], a[ right ] );
	if( a[ right ] < a[ center ] )
		std::swap( a[ center ], a[ right ] );

 // Place pivot at position right - 1
	std::swap( a[ center ], a[ right - 1 ] );
	return a[ right - 1 ];
}
template <typename Iterator, typename Comparator>
void insertionSort(Comparator lessThan , const Iterator & begin, const Iterator & end)
{
	if( begin == end )
		return;

	Iterator j;

	for( Iterator p = begin+1; p != end; ++p )
	{
		auto tmp = std::move( *p );
		for( j = p; j != begin && lessThan( tmp, *( j-1 ) ); --j )
			*j = std::move( *(j-1) );
		*j = std::move( tmp );
	}
}
template <typename Comparable>
void quicksort( vector<Comparable> & a, int left, int right )
{
	if( left + 10 <= right )
	{
		const Comparable & pivot = median3( a, left, right );

			// Begin partitioning
		int i = left, j = right - 1;
		for( ; ; )
		{
			while( a[ ++i ] < pivot ) { }
			while( pivot < a[ --j ] ) { }
			if( i < j )
				std::swap( a[ i ], a[ j ] );
			else
				break;
		}

		std::swap( a[ i ], a[ right - 1 ] ); // Restore pivot

		quicksort( a, left, i - 1 ); // Sort small elements
		quicksort( a, i + 1, right ); // Sort large elements
	}
	else // Do an insertion sort on the subarray
		insertionSort( a, left, right );
}
